/*	This header file contains the declarations and prototype 
	functions  for  the graph ADT class as developed in  
	Gilberg & Forouzan. It also contains the functions not
	discussed in the text and a debugging function to print 
	a vertex. The text functions are included from separate
	header files at the end of this file.

	   Written by: G & F
	   Date:       2/98
	
	   Revised:    5/99 Converted to C++
	
	Brooks/Cole
	A division of Thomson Learning
	Copyright(c) 2001. All Rights Reserved
*/
#define DEBUG 1                  //On includes printVertex

//  ################# Program 12-1 graphs ################ 
	
#include "queueADT"
#include "stackADT"

//	==================== STRUCTURES ====================
template <class TYPE>
struct Vertex;

template <class TYPE>
struct Arc;

template <class TYPE> 
struct Vertex
	{
	 Vertex<TYPE>  *pNextVertex;
	 TYPE           data;
	 int            inDegree;
	 int            outDegree;
	 short          processed;
	 Arc<TYPE>     *pArc;
	}; // Vertex

template <class TYPE>
struct Arc
	{
	 Vertex<TYPE>       *destination;
	 Arc<TYPE>          *pNextArc;
	};	// Arc

template <class TYPE, class KTYPE> 
class Graph
	{
	 private:
	   int     count; 
	   Vertex<TYPE>   *first; 

	 public:
	   Graph  (void);
	  ~Graph  (void);
             
	   int  insertVertex   (TYPE dataIn);
	   int  deleteVertex   (KTYPE dltKey);
	   int  insertArc      (KTYPE  fromKey, KTYPE  toKey);
	   int  deleteArc      (KTYPE  fromKey, KTYPE  toKey);
	   int  retrieveVertex (KTYPE  key,     TYPE& DataOut);
	   int  firstArc       (KTYPE  key,     TYPE& DataOut);
	   bool emptyGraph     (void);
	   bool graphFull      (void);
	   int  graphCount     (void);

	   void depthFirst     (void (*process)(TYPE dataProc));
	   void breadthFirst   (void (*process)(TYPE dataProc));

#ifdef DEBUG              
	   // The following function is used only for debugging
	   void printVertex    (KTYPE  key);
#endif
	}; // Graph 
	
/*	======================= NON-TEXT FUNCTIONS ======================= */
/*	======================= NON-TEXT FUNCTIONS ======================= */
/*	======================= NON-TEXT FUNCTIONS ======================= */


/*	=================== Constructor  ==================
	Instantiated and initializes ADT Class.
	   Pre    Nothing
	   Post   Class instantiated and initialized
*/

template <class TYPE, class KTYPE> 
Graph<TYPE, KTYPE> :: Graph (void)
{
// 	Statements 
	first  = NULL;
	count  = 0;
}	// Constructor 

/*	==================== emptyGraph =================== 
	Returns true if graph is empty, false if any data.
	   Pre   Nothing
	   Post  returns boolean
*/

template <class TYPE, class KTYPE> 
bool Graph<TYPE, KTYPE> :: emptyGraph (void)
{
	return (count == 0);
}	// emptyGraph 

/*	==================== graphFull =================== 
	If there is no room for another node, returns true.
	   Pre      Nothing
	   Returns  true if structure full; false if room
*/

template <class TYPE, class KTYPE> 
bool Graph<TYPE, KTYPE> ::  graphFull (void)
{
//	Local Declarations 
	Vertex<TYPE>  *newPtr;
	
// 	Statements 
	newPtr = new Vertex<TYPE>;
	if (newPtr)
		{
		 delete newPtr;
		 return false;
		} // if 
	else
	    return true;
}	//  graphFull 

/*	=============== graphCount ==============
	Returns number of nodes in graph.
	   Pre   Nothing
	   Post  returns number of nodes in graph
*/

template <class TYPE, class KTYPE> 
int Graph<TYPE, KTYPE> :: graphCount (void)
{
	return (count);
}	// graphCount 

/*	================ retrieveVertex =================== 
	Data contained in vertex identified by key rturned to caller. 
	   Pre    key of the vertex data to be retrieved
              dataOut is a pointer for data pointer
	   Post   Data copied to dataOut
       Return Success +1 if successful
                      -1 if empty list
                      -2 if fromKey not found
*/

template <class TYPE, class KTYPE> 
int Graph<TYPE, KTYPE> :: retrieveVertex (KTYPE key, TYPE& dataOut)
{
//	Local Declarations 
    Vertex<TYPE> *walkPtr;

//	Statements 
	if (!first)
	    return -1;
	
	walkPtr = first;
	while (walkPtr && key > (walkPtr->data).key)
	    walkPtr = walkPtr->pNextVertex;
	if (key == (walkPtr->data).key)
	   {
	    dataOut = walkPtr->data;
	    return 1;
	   } //  if 
	else
	   return -2;
}	// retrieveVertex 
 
/*	==================== firstArc =======================
	Key of first arc from vertex is located and data 
	passed back to caller. 
	   Pre    key of the vertex data
              dataOut is a pointer for data pointer
	   Post   Vertex data pointer copied to pDataOut
       Return Success +1 if successful
                      -1 null graph
                      -2 if fromKey not found
                      -3 no destination key (no arc)
*/


template <class TYPE, class KTYPE> 
int Graph<TYPE, KTYPE> :: firstArc (KTYPE key,   TYPE& dataOut)
{
//	Local Declarations 
    Vertex<TYPE>  *walkPtr;
    
    Arc<TYPE>    *toPtr;

//	Statements 
	if (!first)
	    return -1;
	
	walkPtr = first;
	while (walkPtr && key > walkPtr->data.key)
	    walkPtr = walkPtr->pNextVertex;
	if (key == (walkPtr->data).key)
	   {
	    if (walkPtr->pArc)
	       {
	        toPtr     = walkPtr->pArc;
	        dataOut = toPtr->destination->data;
	        return 1;
	       } // if walkPtr 
	    else
	        return -3;
	   } // if found 
	else
	   return -2;
}	// firstArc 

/*	=============== Destructor  ==============
	Deletes any data in graph.
	   Pre   Graph ADT Class being destroyed
	   Post  All dynamic memory elements freed
*/

template <class TYPE, class KTYPE> 
Graph<TYPE, KTYPE> :: ~Graph (void)
{
//	Local Declarations
	Vertex<TYPE>  *verDltPtr;
	Arc<TYPE>     *arcDltPtr;

//	Statements 
	if (first)
	   {
	    while (count > 0)
	       {
	        verDltPtr = first;
	        first     = first->pNextVertex;
	        while (verDltPtr->pArc)
	           {           
	            arcDltPtr        = verDltPtr->pArc;
	            verDltPtr->pArc  = arcDltPtr->pNextArc;
	            delete arcDltPtr;
	           } // while (verDltPtr->pArc)
	        delete verDltPtr;
	        count--;
	       } // while (count >0)
	   } //if
}	// Destructor 

/*	======================= END GRAPH ADT ======================= */
/*	======================= END GRAPH ADT ======================= */
/*	======================= END GRAPH ADT ======================= */

#if (DEBUG)
/*	The following functions are not part of the ADT. They are 
	included to provide debugging output.
*/

/*  ============================= printVertex ============================= 
	This function prints a graph vertex and its adjacency list 
	
	NOTE: THIS IS NOT AN APPLICATION ADT FUNCTION. IT IS 
	USED ONLY FOR DEBUGGING PURPOSES.
	
	   Pre  key of vertex to be printed
	   Post Adjacency list has been printed
*/
template <class TYPE, class KTYPE> 
void Graph<TYPE, KTYPE> :: printVertex (KTYPE  key) 
{
/*	Local Declarations */
	Vertex<TYPE> *pVertexWalk;
	
	Arc<TYPE>   *pArcWalk;
//	void  *pVoid;
	
/*  Statements */
	/* Locate vertex */
	pVertexWalk = first;
	while (pVertexWalk && key > (pVertexWalk->data).key)
	    pVertexWalk = pVertexWalk->pNextVertex;
	if (!pVertexWalk || (key != (pVertexWalk->data).key))
	   {
	    cout << "\aVertex " << key << " does not exist\n";
	    return;
	   } /* if !pVertex || */
	
	cout << "Adjacency list for " << setw(2) << key;
	cout << ": inDegree "  << setw(2) << pVertexWalk->inDegree
	     << "--outDegree " << setw(2) << pVertexWalk->outDegree
	     << endl;

	pArcWalk = pVertexWalk->pArc; 
	while (pArcWalk)
	    {
	     cout << setw(4) << pArcWalk->destination->data.key;	             
	     pArcWalk = pArcWalk->pNextArc;
	    } // while 
    return;
}   // printVertex 
#endif

#include "P12-02"
#include "P12-03"
#include "P12-04"
#include "P12-05"
#include "P12-06"
#include "P12-07"

//	==================== End of p12Graph.h Library ==================== 




